对抗性搜索与约束满足

欢迎来到第 3 讲人工智能概念（PolyU COMP5511）。在本讲中，我们将从单智能体寻路过渡到对抗性搜索，智能体在竞争性多智能体环境中运行。我们还将介绍约束满足问题 (CSPs)，这是一种范式，目标是找到一个满足特定限制条件的状态，而不是一条路径。

核心概念

对抗性搜索： 专注于像 Minimax 和 Alpha-Beta 剪枝这样的算法，以对抗智能对手并做出理性决策。
蒙特卡洛树搜索 (MCTS)： 探索概率性决策，是现代游戏 AI（如 AlphaGo）的支柱。
约束满足： 使用变量、域和约束来建模问题，通过 回溯法 和 局部搜索）的支柱。

复杂度分析

在对抗性环境中，搜索空间复杂度通常由游戏的分支因子 $b$ 和深度 $d$ 决定，导致计算成本为： $O （ b^{d} ）$ 这种指数级增长需要高效的剪枝策略，例如 Alpha-Beta 剪枝。

范式转变警告

与标准搜索（例如 A* 或 BFS）中环境是静态的 对抗性搜索 不同，我们假设环境（对手）会积极地试图最小化你的成功。在 CSPs 中，操作的顺序不如最终赋值的有效性重要。

概念伪代码：智能体类型

# 对抗性智能体（博弈论）
functionDecide_Move（state):
returnMaximize_Utility（Predict_Opponent_Minimization（state))
# CSP 求解器（约束逻辑）
functionSolve_CSP（variables, constraints):
ifAll_Constraints_Satisfied（assignment):
returnassignment
else：
returnBacktrack_Search（variables）

课程路线图

从搜索（第 2 讲）过渡到战略决策（第 3 讲）。